package 代码记录.Bit48天集训;

import java.util.Scanner;

/**编程题已搞定
 * 1.求正数数组的最小不可组成和(01背包)
 * 2.有假币
 * @author zx
 * @create 2022-05-27 9:02
 */
public class day_29 {
    public int getFirstUnFormedNum(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = 0;
        for(int i = 0;i < arr.length;i++){
            min = Math.min(min,arr[i]);
            max += arr[i];
        }
        int[] dp = new int[max + 1];
        for(int i = 0;i < arr.length;i++){
            for(int j = max;j >= min;j--){
                if(j >= arr[i]){
                    dp[j] = Math.max(dp[j],dp[j - arr[i]] + arr[i]);
                }
            }
        }
        for(int i = min;i <= max;i++){
            if(dp[i] != i){
                return i;
            }
        }
        return max + 1;
    }
    /**
     当n = 1时，不需要再称了，它就是假币，总共需要0次
     当n = 2时，1、1放天平两端，轻的就是假币，总共需要1次
     当n = 3时，随机抽出2个放到天平两端，如果天平平衡，则剩下1个就是假币，
     否则天平中较轻的是假币，总共需要1次
     当n = 4时，分成1、1、2，天平秤1、1，注意题目要求最短时间，
     并且是次数最大的情况，也就是我们需要考虑最坏的情况，第一次1、1重量相等，
     接着我们把2分开称，总共需要2次
     当n = 5时，分成2、2、1，天平秤2、2，同样考虑最坏的情况，2、2重量相等，
     接着我们把2分开称，总共需要2次
     当n = 6时，分成2、2、2，天平秤2、2，同样考虑最坏的情况，不管如何，还需要
     把2分开称，总共需要2次
     当n = 7时，分成2、2、3，天平先称2、2，考虑最坏的情况，重量相等，接着我们就需要
     按照n = 3的最优情况称，总共需要2次
     ...
     其中有一个规则，我们每次把n分成是3堆，
     如果n % 3 == 0,分成 n/3、 n/3、 n/3三堆， 剩下 n/3
     如果n % 3 == 1,分成 n/3、 n/3、1 + (n/3)三堆，最坏剩下 1 + (n/3)
     如果n % 3 == 2,分成 n/3、 1 + (n/3)、1 + (n/3)三堆，最坏剩下 1 + (n/3)
     */
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            if(n == 0){
                break;
            }
            int count = 0;
            while (n > 1) {
                count += 1;
                //每次取1/3,如果不能整除3，有两种情况
                //剩余1个，分成 1/3 、1/3 、1 + (1/3) ，两个1/3放入天平两端，
                //剩余2个，分成 1/3 、1 + (1/3) 、 1 + (1/3)，两个1 + (1/3)放入天平两端
                //由于题目要求最快的时间，并且是求最多的次数，因此取每次剩余的最大值 1 + (1/3)
                int flag = n % 3 > 0 ? 1 : 0;
                n = n / 3 + flag;
            }
            System.out.println(count);
        }
    }
}
